package leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wangmaolin1
 * @date 2023/11/11 11:49
 */
public class _889 {
    private Map<Integer, Integer> postVal2Index = new HashMap<>();

    /**
     * 给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
     * <p>
     * 如果存在多个答案，您可以返回其中 任何 一个。
     */
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++) {
            postVal2Index.put(postorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
    }

    /**
     * 1. 确定根节点
     * 2. 把先序第二个节点当做左节点
     * 3.从后序中找到左节点位置，确认后序的左子树范围，和右子树范围
     * 4.从后序可计算出左子树节点个数，就能计算出先序的左子树范围和右子树范围
     */
    public TreeNode build(int[] preOrder, int preStart, int preEnd, int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd || preEnd >= preOrder.length | postStart > postEnd || postEnd >= postorder.length) {
            return null;
        }
        int rootVal = preOrder[preStart];
        TreeNode root = new TreeNode(rootVal);
        if (preStart ==preEnd) {
            return root;
        }

        Integer leftIndex = postVal2Index.get(preOrder[preStart + 1]);
        int leftTreeNodeNum = leftIndex - postStart + 1;


        root.left = build(preOrder, preStart + 1, preStart + leftTreeNodeNum, postorder, postStart, leftIndex);
        root.right = build(preOrder, preStart + leftTreeNodeNum + 1, preEnd, postorder, leftIndex + 1, postEnd - 1);
        return root;
    }
}
